Voice messages, such as voicemail messages, are typically left for a call recipient when the recipient does not answer his or her telephone. In such situations, voicemail messages are left by a caller more or less in real time with placing a call to the call recipient. Sometime later, the call recipient may contact a voicemail server to retrieve voicemail messages.